package com.leetcode.medium;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class AddTwoNumbers {
    //version 1
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode((l1.val+l2.val)%10);
        ListNode p1 = l1.next,p2 = l2.next,p = result;
        int carry = 0;
        if(l1.val + l2.val >= 10) carry = 1;
        while (p1 != null || p2 != null) {
            int nextVal = ((p1 != null)?p1.val:0)+ ((p2 != null)?p2.val:0) + carry;
            ListNode next = new ListNode(nextVal % 10);
            carry = (nextVal >= 10) ? 1 : 0;
            p.next = next;
            p = p.next;
            if(p1 != null) p1 = p1.next;
            if(p2 != null) p2 = p2.next;
        }
        if(carry == 1)
            p.next = new ListNode(1);
        return result;
    }

    //version 2
    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode r = new ListNode((l1.val+l2.val) % 10);
        int c = (l1.val+l2.val) > 9? 1 : 0;
        l1 = l1.next;
        l2 = l2.next;
        ListNode p = r;
        while (l1 != null && l2 != null) {
            int nextVal = l1.val + l2.val + c;
            c = nextVal > 9 ? 1 : 0;
            ListNode next = new ListNode(nextVal % 10);
            p.next = next;
            p = p.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        ListNode left = (l1 == null)?l2:l1;
        if(c == 0)
            p.next = left;
        else {
            while (left != null) {
                int nextVal = left.val + c;
                c = nextVal > 9 ? 1 : 0;
                ListNode next = new ListNode(nextVal % 10);
                p.next = next;
                p = p.next;
                left = left.next;
            }
            if(c == 1)
                p.next = new ListNode(1);
        }
        return r;
    }

    public static void main(String [] args) {
        ListNode l1 = new ListNode(9);
        ListNode l2 = new ListNode(9);
        ListNode l3 = new ListNode(9);

        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(6);
        ListNode n3 = new ListNode(4);

        l1.next = l2; l2.next = l3; l3.next = null;
        n1.next = n2; n2.next = n3; n3.next = null;
        ListNode r = addTwoNumbers2(l1,n1);
        for(ListNode p = r; p != null; p = p.next) {
            System.out.print(p.val+"\t");
        }
    }
}
